package com.gxc.stack;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 字符串解码
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 */
public class DecodeString {

    public String decodeString(String s) {
        Stack<Integer> number = new Stack<>();
        Stack<String> string = new Stack<>();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c - '0'>0 && c-'0'<=9) {
                int l = i;
                while (c - '0'>=0 && c-'0'<=9) {
                    i++;
                    c = s.charAt(i);
                }
                number.push(Integer.valueOf(s.substring(l, i)));
                i--;
            } else if (c == ']'){
                StringBuilder str = new StringBuilder();
                while (!string.peek().equals("[")) {
                    str.append(string.pop());
                }
                string.pop();
                Integer n = number.pop();
                String res = str.toString();
                for (int j = 0; j < n; j++) {
                    string.push(res);
                }
            } else {
                string.push(String.valueOf(c));
            }
        }
        while (!string.isEmpty()) builder.append(string.pop());
        return builder.reverse().toString();
    }

    public String decodeString2(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }

}
